import java.lang.reflect.Array;
import java.util.*;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-02-08
 * Time:19:00
 */
/**
 * 1001. 网格照明
 * 在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态。
 *
 * 给你一个由灯的位置组成的二维数组 lamps ，其中 lamps[i] = [rowi, coli] 表示 打开 位于 grid[rowi][coli] 的灯。即便同一盏灯可能在 lamps 中多次列出，不会影响这盏灯处于 打开 状态。
 *
 * 当一盏灯处于打开状态，它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 。
 *
 * 另给你一个二维数组 queries ，其中 queries[j] = [rowj, colj] 。对于第 j 个查询，如果单元格 [rowj, colj] 是被照亮的，则查询结果为 1 ，否则为 0 。在第 j 次查询之后 [按照查询的顺序] ，关闭 位于单元格 grid[rowj][colj] 上及相邻 8 个方向上（与单元格 grid[rowi][coli] 共享角或边）的任何灯。
 *
 * 返回一个整数数组 ans 作为答案， ans[j] 应等于第 j 次查询 queries[j] 的结果，1 表示照亮，0 表示未照亮。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/grid-illumination
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 方法一：哈希表
 * 思路与算法
 *
 * 将网格转换成一个坐标系，行下标作为 xx 坐标，列下标作为 yy 坐标。我们使用直线与坐标轴上交点的数值来唯一标识行，列和正/反对角线。相应的规则为：
 *
 * 求解通过灯坐标的行直线与 xx 轴的交点，将交点的 xx 坐标作为通过灯坐标的行的数值。
 * 求解通过灯坐标的列直线与 yy 轴的交点，将交点的 yy 坐标作为通过灯坐标的列的数值。
 * 求解通过灯坐标的正对角线与 xx 轴的交点，将交点的 xx 坐标作为通过灯坐标的正对角线的数值。
 * 求解通过灯坐标的反对角线与 yy 轴的交点，将交点的 yy 坐标作为通过灯坐标的反对角线的数值。
 *
 * 假设一盏灯的坐标为 (x_i,~y_i)(x_i,y_i)，那么它所在的行的数值为 x_i，列的数值为 y_i，
 * 正对角线的数值为 x_i-y_i,
 * 反对角线的数值为 x_i+y_i。确定某一直线的唯一数值标识后，我们就可以通过哈希表来记录某一直线所拥有的灯的数目。
 *
 * 遍历 \textit{lamps}lamps，将当前遍历到的灯所在的行，列和正/反对角线拥有灯的数目分别加一。
 *
 * 在处理 \textit{lamps}lamps 时，需要进行去重，因为我们将重复的灯看作同一盏灯。
 *
 * 遍历 \textit{queries}queries，判断当前查询点所在的行，列和正/反对角线是否有灯，如果有，则置 11，即该点在查询时是被照亮的。然后进行关闭操作，查找查询点所在的八近邻点及它本身是否有灯，如果有，将该点所在的行，列和正/反对角线的灯数目分别减一，并且将灯从网格中去掉。
 *
 *  */
public class TestDemo {
    public static long hash(int x, int y) {
        return (long) x + ((long) y << 32);
    }

    public static int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        Map<Integer, Integer> row = new HashMap<>();
        Map<Integer, Integer> col = new HashMap<>();
        Map<Integer, Integer> diagonal = new HashMap<>();
        Map<Integer, Integer> antDiagonal = new HashMap<>();
        Set<Long> points = new HashSet<>();
        for (int[] lamp : lamps) {
            if (points.contains(hash(lamp[0], lamp[1]))) {
                continue;
            } else {
                points.add(hash(lamp[0], lamp[1]));
            }
            row.put(lamp[0], row.getOrDefault(lamp[0], 0) + 1);
            col.put(lamp[1], col.getOrDefault(lamp[1], 0) + 1);
            diagonal.put(lamp[0] - lamp[1], diagonal.getOrDefault(lamp[0] - lamp[1], 0) + 1);
            antDiagonal.put(lamp[0] + lamp[1], antDiagonal.getOrDefault(lamp[0] + lamp[1], 0) + 1);
        }
        int[] ret = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int r = queries[i][0];
            int c = queries[i][1];
            if (row.getOrDefault(r, 0) > 0) {
                ret[i] = 1;
            } else if (col.getOrDefault(c, 0) > 0) {
                ret[i] = 1;
            } else if (diagonal.getOrDefault(r - c, 0) > 0) {
                ret[i] = 1;
            } else if (antDiagonal.getOrDefault(r + c, 0) > 0) {
                ret[i] = 1;
            }

            for (int x = r - 1; x <= r + 1; x++) {
                for (int y = c - 1; y <= c + 1; y++) {
                    if (x < 0 || y < 0 || x >= n || y >= n) {
                        continue;
                    }
                    if (points.remove(hash(x, y))) {
                        row.put(x, row.get(x) - 1);
                        if (row.get(x) == 0) {
                            row.remove(x);
                        }
                        col.put(y, col.get(y) - 1);
                        if (col.get(y) == 0) {
                            col.remove(y);
                        }
                        diagonal.put(x - y, diagonal.get(x - y) - 1);
                        if (diagonal.get(x - y) == 0) {
                            diagonal.remove(x - y);
                        }
                        antDiagonal.put(x + y, antDiagonal.get(x + y) - 1);
                        if (antDiagonal.get(x + y) == 0) {
                            antDiagonal.remove(x + y);
                        }
                    }
                }
            }
        }
        return ret;
    }
    public int[] gridIllumination2(int n, int[][] lamps, int[][] queries) {
        //存储行被照亮的次数
        Map<Integer, Integer> row = new HashMap<>();
        //存储列被照亮的次数
        Map<Integer, Integer> col = new HashMap<>();
        //存储正对角线被照亮的次数
        Map<Integer, Integer> diagonal = new HashMap<>();
        //存储反对角线被照亮的次数
        Map<Integer, Integer> antDiagonal = new HashMap<>();
        //存储被打开的灯;若重复打开等则不存储,因为题目中说了同一盏等即使多次被打开,不影响该灯处于
        //打开状态;即无论重复打开同一盏灯多少次,改灯都为开灯状态
        Set<Long> points = new HashSet<>();
        //遍历开灯数组
        for (int[] lamp : lamps) {
            //若灯已经是打开状态;则跳过本次循环进行下一次循环
            if (points.contains(hash(lamp[0], lamp[1]))) {
                continue;
            } else {
                //若灯没打开则hash过后入Set;
                points.add(hash(lamp[0], lamp[1]));
            }
            //灯第一次打开,则改行被照亮的次数加1
            row.put(lamp[0], row.getOrDefault(lamp[0], 0) + 1);
            //灯第一次打开,则改列被照亮的次数加1
            col.put(lamp[1], col.getOrDefault(lamp[1], 0) + 1);
            //灯第一次打开,则改正对角线被照亮的次数加1
            diagonal.put(lamp[0] - lamp[1], diagonal.getOrDefault(lamp[0] - lamp[1], 0) + 1);
            //灯第一次打开,则改反对角线被照亮的次数加1
            antDiagonal.put(lamp[0] + lamp[1], antDiagonal.getOrDefault(lamp[0] + lamp[1], 0) + 1);
        }
        //记录答案的数组
        int[] ret = new int[queries.length];
        //遍历关灯数组
        for (int i = 0; i < queries.length; i++) {
            //记录行
            int r = queries[i][0];
            //记录列
            int c = queries[i][1];
            //若行或列或正对角或反对角线被照亮的次数大于1;则说明该位置是被照亮的;ret记录该位置为1
            if (row.getOrDefault(r, 0) > 0) {
                ret[i] = 1;
            } else if (col.getOrDefault(c, 0) > 0) {
                ret[i] = 1;
            } else if (diagonal.getOrDefault(r - c, 0) > 0) {
                ret[i] = 1;
            } else if (antDiagonal.getOrDefault(r + c, 0) > 0) {
                ret[i] = 1;
            }
            //关灯循环
            for (int x = r - 1; x <= r + 1; x++) {
                for (int y = c - 1; y <= c + 1; y++) {
                    //不在表格范围内的数据
                    if (x < 0 || y < 0 || x >= n || y >= n) {
                        continue;
                    }
                    //关掉该盏灯
                    if (points.remove(hash(x, y))) {
                        //把该行被照亮的次数减1;
                        row.put(x, row.get(x) - 1);
                        if (row.get(x) == 0) {
                            row.remove(x);
                        }
                        //把该列被照亮的次数减1;
                        col.put(y, col.get(y) - 1);
                        if (col.get(y) == 0) {
                            col.remove(y);
                        }
                        //把该正对角线被照亮的次数减1;
                        diagonal.put(x - y, diagonal.get(x - y) - 1);
                        if (diagonal.get(x - y) == 0) {
                            diagonal.remove(x - y);
                        }
                        //把该反对角线被照亮的次数减1;
                        antDiagonal.put(x + y, antDiagonal.get(x + y) - 1);
                        if (antDiagonal.get(x + y) == 0) {
                            antDiagonal.remove(x + y);
                        }
                    }
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int[][] num = {{0,0},{4,4}};
        int[][] p = {{1,1},{1,1}};
        System.out.println(Arrays.toString(gridIllumination(5, num, p)));
    }
}
